package 力扣.回溯;

import java.util.ArrayList;
import java.util.List;

public class 字母大小写全排列784 {
    public List<String> letterCasePermutation(String S) {
         if(S == null || S.length() == 0){
             return new ArrayList<>();
         }
         List<String> ans= new ArrayList<String>();
        StringBuilder box = new StringBuilder();
        backTrace(S,0,ans,box);
        return ans;
    }

    private void backTrace(String s, int i, List<String> ans, StringBuilder box) {
        final int N = s == null ? 0:s.length();
        if (i == N){//查看当前状态并判断当前状态是否满足答案要求
            ans.add(box.toString());
        }
        if (i >= N){//查看这个人存不存在
            return;
        }
        //若存在，看宝石的选项是啥，并把它装进来
        //判断是否是字母
        char c = s.charAt(i);
        if (c < 65){
            box.append(c);
            backTrace(s, i + 1, ans, box);
            box.deleteCharAt(box.length() - 1);
        }else {
            for (int j = 0; j < 2; j++) {
                c = c >= 97 ? (char) (c - 32) : (char) (c + 32);
                box.append(c);
                backTrace(s, i + 1, ans, box);
                box.deleteCharAt(box.length() - 1);
            }
        }
    }
}
